package base;

/**
 * @author 何昌杰
 */
public class Base6 {

    /**
     *将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     *
     * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
     *
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
     *
     * 请你实现这个将字符串进行指定行数变换的函数：
     *
     * string convert(string s, int numRows);
     *  
     *
     * 示例 1：
     *
     * 输入：s = "PAYPALISHIRING", numRows = 3
     * 输出："PAHNAPLSIIGYIR"
     * 示例 2：
     * 输入：s = "PAYPALISHIRING", numRows = 4
     * 输出："PINALSIGYAHRPI"
     * 解释：
     * P     I    N
     * A   L S  I G
     * Y A   H R
     * P     I
     * 示例 3：
     *
     * 输入：s = "A", numRows = 1
     * 输出："A"
     *  
     *
     * 提示：
     *
     * 1 <= s.length <= 1000
     * s 由英文字母（小写和大写）、',' 和 '.' 组成
     * 1 <= numRows <= 1000
     *
     */
    public static void main(String[] args) {
        System.out.println(zConvert("PAYPALISHIRING", 4));
        System.out.println(zConvert("Apalindromeisaword,phrase,number,orothersequenceofunitsthatcanbereadthesamewayineitherdirection,withgeneralallowancesforadjustmentstopunctuationandworddividers.", 4));
        System.out.println(zConvert2("Apalindromeisaword,phrase,number,orothersequenceofunitsthatcanbereadthesamewayineitherdirection,withgeneralallowancesforadjustmentstopunctuationandworddividers.", 4));
    }

    static String zConvert(String s, int numRows) {
        if(s == null || s.length() == 0 || numRows == 1){
            return s;
        }
        int n = ( numRows - 1) * s.length() / ( 2 * numRows - 2) + ( numRows - 1);
        Character[][] ar = new Character[numRows][n];
        char[] charArray = s.toCharArray();
        int tp = 0;
        for(int j = 0; j < n; j++ ){
            for(int i = 0; i < numRows; i++){
                if(tp == s.length()){
                    break;
                }
                if(j % (numRows - 1) == 0){
                    ar[i][j] = charArray[tp++];
                } else {
                    ar[numRows - 1 - j % (numRows - 1)][j] = charArray[tp++];
                    break;
                }
            }
        }

        char[] re = new char[s.length()];
        tp = 0;
        for(int i = 0; i < numRows; i++ ){
            for(int j = 0; j < n; j++){
                if(ar[i][j] != null){
                    re[tp++] = ar[i][j];
                }
            }
        }

        return new String(re);
    }

    static String zConvert2(String s, int numRows) {
        if(s == null || s.length() == 0 || numRows == 1){
            return s;
        }
        int i = 0, len = s.length(), n = numRows - 1, t = 2 * numRows - 2, th = t / 2, index;
        char[] re = new char[len], arr = s.toCharArray();
        int[] count = new int[numRows];
        int j = 0;
        while(i < numRows){
            if(i == 0){
                while(true){
                    index = count[0] * t;
                    count[0]+=1;
                    if(index < len){
                        re[j++] = arr[index];
                    } else {
                        break;
                    }
                }
            }else if( i < th){
                boolean judge = true;
                int c = (2 * n - i);
                while(true){
                    index = judge ? i + count[i] * t : c + count[i] * t;
                    if(!judge){
                        count[i]+=1;
                    }
                    judge = !judge;
                    if(index < len){
                        re[j++] = arr[index];
                    } else {
                        break;
                    }
                }
            } else {
                while(true){
                    index = n + count[n] * t;
                    count[n]+=1;
                    if(index < len){
                        re[j++] = arr[index];
                    } else {
                        break;
                    }
                }
            }
            i++;
        }
        return new String(re);
    }
}
